package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-12 23:01
 */
public class ClimbStair {
    /** leetcode 70
     * 五部曲：1.dp数组，每一个元素的下标代表爬楼梯的层数，每一个元素代表到达该层有多少种方法2.地推公式：dp[n]=dp[n-1]+dp[n-2]
     * 3.dp数组的初始化 dp[0]=0;表示达到0台阶没有方法（本身就在），dp[1]=1,dp[2]=2 4.遍历顺序，有递推公式可得，前推后，所以是从前往后遍历
     * @return
     */
    public static int climb(int n){
        //初始化
        int[]dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        //进行遍历
        for(int i=2;i<=n;++i){
            dp[i]=dp[n-1]+dp[n-2];
        }
        return dp[n];
    }
}
